package 树;

public class Leedcode426二叉排序树转有序双向链表 {
    public static void main(String[] args) {
        NodeTree root = new NodeTree(3);
        NodeTree node1 = new NodeTree(2);
        NodeTree node2 = new NodeTree(1);
        NodeTree node3 = new NodeTree(4);
        NodeTree node4 = new NodeTree(5);
        root.left = node1;
        node1.left = node2;
        root.right = node3;
        node3.right = node4;
        NodeTree node = treeHelper(root);
        int i = 0;
        while (node != null && i < 5){
            System.out.print(node.val+" ");
            node = node.right;
            i++;
        }
    }

    public static NodeTree treeToDoublyList(NodeTree root){
        //如果节点为空，则直接返回
        if (root == null){
            return null;
        }
        //否则将二叉树先转换成双向链表，此时的链表为双向链表，不是环形链表
        NodeTree node = treeHelper(root);
        NodeTree flag = node;
        //在转换成环形链表，找到链表的尾节点
        while (flag != null && flag.right != null){
            flag = flag.right;
        }
        //将首尾相连
        node.left = flag;
        flag.right = node;

        return node;
    }


    /**
     * 传入一个二叉树节点，我就可以将二叉树转换成双向链表返回链表的头节点
     * @param root
     * @return
     */
    public static NodeTree treeHelper(NodeTree root) {
        //如果节点为空，直接返回null
        if(root == null){
            return null;
        }
        //否则将二叉树的左子树交给具有该功能的方法执行
        NodeTree leftHead = treeHelper(root.left);
        //执行完成，现在二叉树的左子树已经为有序的双向链表
        //遍历找到左子树的尾节点
        NodeTree leftTail = leftHead;
        while (leftTail != null && leftTail.right != null){
            leftTail = leftTail.right;
        }
        //如果尾节点不为空，将尾节点和根节点进行拼接
        if (leftTail != null){
            leftTail.right = root;
            root.left = leftTail;
        }
        //在将二叉树的右子树交给具有该功能的方法，转换成双向链表，
        NodeTree rightHead = treeHelper(root.right);
        //如果右子树转为的链表不为空，进行拼接
        if (rightHead != null){
            rightHead.left = root;
            root.right = rightHead;
        }
        //拼接完成后，返回双向链表
        return leftHead == null ? root : leftHead;
    }
}
class Node {
    public int val;
    public NodeTree left;
    public NodeTree right;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, NodeTree _left, NodeTree _right) {
        val = _val;
        left = _left;
        right = _right;
    }
}